package lib

func init() {
	Probs = append(Probs, Problem{
		Num:         875,
		Discription: "给n捆香蕉，每小时只能选择一捆吃，每小时最多吃k个，求在h小时内吃完所有香蕉的最小k",
		Level:       2,
		Labels: map[string]int{
			"二分查找": 1,
			"向上取整": 1,
		},
	})
}

func MinEatingSpeed(piles []int, h int) int {
	if len(piles) == 0 {
		return 0
	}

	//求最大的速率：也就是每捆香蕉都能一次性吃完的最小速率
	maxV := piles[0]
	for i := 1; i < len(piles); i++ {
		maxV = max(maxV, piles[i])
	}

	//遍历一次，向上取整统计吃完所有香蕉要几个小时
	calTime := func(v int) int {
		res := 0
		for _, pile := range piles {
			res += (pile + v - 1) / v
		}

		return res
	}

	left := 1
	right := maxV
	for left < right {
		mid := left + (right-left)/2
		//等于h的时候，最终的答案也有可能是当前的mid的，所以right=mid
		if calTime(mid) <= h {
			right = mid
		} else {
			left = mid + 1
		}
	}

	return left
}
